package BinaryTree;//检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
//
// 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。 
//
// 注意：此题相对书上原题略有改动。 
//
// 示例1: 
//
// 
// 输入：t1 = [1, 2, 3], t2 = [2]
// 输出：true
// 
//
// 示例2: 
//
// 
// 输入：t1 = [1, null, 2, 4], t2 = [3, 2]
// 输出：false
// 
//
// 提示： 
//
// 
// 树的节点数目范围为[0, 20000]。 
// 
// Related Topics 树 深度优先搜索 二叉树 字符串匹配 哈希函数 👍 56 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class checkSubTree {
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if(t1==null || t2==null){
            return false;
        }
        //递归从当前节点和B比较，孩子节点和B比较，结果取或，只要有一个满足即可
        return dfs(t1,t2) || checkSubTree(t1.left,t2) || checkSubTree(t1.right,t2);
    }

    public boolean dfs(TreeNode A, TreeNode B){
        //因为外面已经判断B 不能为null，所以进来递归后为null说明到一个路径得末尾,即成功比较一边2
        if(B==null){
            return true;
        }
        //A为null B不为null，说明已经超出A的叶子节点，肯定不相等
        if(A==null){
            return false;
        }

        boolean left = dfs(A.left,B.left);
        boolean right = dfs(A.right,B.right);

        return A.val==B.val && left && right;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
